package jp.sourceforge.talisman.mds;

/*
 * $Id: MdsMethod.java,v 1.3 2010/02/08 16:05:53 weiwei Exp $
 */

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

import Jama.EigenvalueDecomposition;
import Jama.Matrix;

/**
 * This class is an implementation of MDS (Multi-Dimensional Scaling)
 * method.  MDS is an analysis method, which is to display
 * differences among items for visualization in 2 or 3 dimensional
 * space.
 * 
 * @author Haruaki Tamada
 * @version $Revision: 1.3 $ 
 */
public class MdsMethod<T> implements Iterable<Item>{
    private boolean calculated = false;
    private Table<T> table;
    private int rank;
    private int limit = -1;
    private Map<String, Item> itemsMap = new LinkedHashMap<String, Item>();

    /**
     * default constructor.  Call {@link setSheet
     * <code>setTable</code>} method at first, when this constructor
     * is used.
     */
    public MdsMethod(){
    }

    /**
     * self constructor.
     */
    public MdsMethod(MdsMethod<T> mds){
        this(mds.getTable());
    }

    /**
     * basic constructor.
     */
    public MdsMethod(Table<T> table){
        this.table = table;
    }

    /**
     * calculate the rank of original relation data set matrix.
     */
    public int getRank(){
        if(!calculated){
            calculate();
        }
        return rank;
    }

    public boolean isLimitted(){
        return limit > 0;
    }

    public void setLimit(int limit){
        if(limit <= 0){
            throw new IllegalArgumentException();
        }
        this.limit = limit;
        if(!calculated){
            calculate();
        }
        for(Item item: this){
            item.setLimit(limit);
        }
    }

    public void removeLimit(){
        limit = -1;
        for(Item item: this){
            item.removeLimit();
        }
    }

    public int getLimit(){
        if(!isLimitted()){
            throw new IllegalStateException();
        }
        return limit;
    }

    /**
     * calculate coordinates.
     * @throws IllegalStateException thrown when table is not valid.
     */
    public void calculate(){
        Table<T> table = getTable();
        if(table == null){
            throw new IllegalStateException();
        }
        if(!table.isValid()){
            throw new IllegalStateException();
        }

        Matrix target = constructTargetMatrix(table);
        Matrix mat = getCenteredInnerProductMatrix(target);

        EigenvalueDecomposition eigen = mat.eig();
        Matrix eigenVectors = eigen.getV();
        Matrix eigenValues  = eigen.getD();
        Matrix itemMatrix   = (Matrix)eigenVectors.clone();

        int col = mat.getColumnDimension();
        int row = mat.getRowDimension();
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                double v = itemMatrix.get(i, j);
                v = v * Math.sqrt(eigenValues.get(j, j));
                itemMatrix.set(i, j, v);
            }
        }
        int[] indexes = sortValues(eigenValues);

        rank = target.rank();
        Object[] labels = table.getKeys();
        for(int i = 0; i < labels.length; i++){
            Item c = new Item(String.valueOf(labels[i]));
            itemsMap.put(c.getName(), c);
            for(int j = 0; j < rank; j++){
                c.add(itemMatrix.get(i, indexes[j]));
            }
        }
        calculated = true;
    }

    /**
     * returns calculated coordinate mapped given label.
     * @throws IllegalStateException thrown when table is not valid.
     */
    public Item getItem(String label){
        if(!calculated){
            calculate();
        }
        return itemsMap.get(label);
    }

    /**
     * returns the number of coordinates.
     * @throws IllegalStateException thrown when table is not valid.
     */
    public int getItemCount(){
        if(!calculated){
            calculate();
        }
        return itemsMap.size();
    }

    /**
     * returns the calculated coordinates.
     * @throws IllegalStateException thrown when table is not valid.
     */
    public synchronized Item[] getItems(){
        Item[] items = new Item[getItemCount()];
        int index = 0;
        for(Item c: this){
            items[index] = c;
            index++;
        }
        return items;
    }

    public Table<T> getTable(){
        return table;
    }

    /**
     * returns the iterator of calculated coordinates.
     * @throws IllegalStateException thrown when table is not valid.
     */
    public Iterator<Item> iterator(){
        if(!calculated){
            calculate();
        }
        return itemsMap.values().iterator();
    }

    /**
     * returns the iterator of coordinate names.
     */
    public Iterator<String> names(){
        if(!calculated){
            calculate();
        }
        return itemsMap.keySet().iterator();
    }

    /**
     * sets a new table as the input of this method.
     */
    public void setTable(Table<T> table){
        this.table = table;
        itemsMap.clear();
        calculated = false;
    }

    /**
     * constructs and returns the relation data matrix from given table. 
     */
    private Matrix constructTargetMatrix(Table<T> table){
        Matrix matrix = new Matrix(table.getKeySize(), table.getKeySize());
        Set<T> names = table.getKeySet();
        int indexX = 0;

        for(T nameX: names){
            int indexY = 0;
            for(T nameY: names){
                if(nameX.equals(nameY)){
                    matrix.set(indexX, indexY, 0d);
                }
                else{
                    Number number = table.getValue(nameX, nameY);
                    matrix.set(indexX, indexY, number.doubleValue());
                }
                indexY++;
            }
            indexX++;
        }
        return matrix;
    }

    private Matrix getCenteredInnerProductMatrix(Matrix target){
        int size = target.getColumnDimension();
        assert target.getRowDimension() == target.getColumnDimension();
        Matrix m = new Matrix(target.getColumnDimension(), target.getRowDimension());
        double v3 = 0d;
        for(int k = 0; k < size; k++){
            for(int l = 0; l < size; l++){
                v3 += target.get(k, l) * target.get(k, l) / (size * size);
            }
        }
        Map<Integer, Double> avgCol = new HashMap<Integer, Double>();
        Map<Integer, Double> avgRow = new HashMap<Integer, Double>();
        for(int i = 0; i < size; i++){
        	double col = 0;
        	double row = 0;
        	for(int j = 0; j < size; j++){
        		col += target.get(j, i) * target.get(j, i);
        		row += target.get(i, j) * target.get(i, j);
        	}
        	col /= size;
        	row /= size;
        	avgCol.put(i, col);
        	avgRow.put(i, row);
        }
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                double v1 = avgCol.get(j);
                double v2 = avgRow.get(i);
                double v4 = target.get(i, j);
                m.set(i, j, (v1 + v2 - v3 - (v4 * v4)) / 2d);
            }
        }
        return m;
    }

    private int[] sortValues(Matrix m){
        double[] v = new double[m.getColumnDimension()];
        int[] index = new int[v.length];
        for(int i = 0; i < v.length; i++){
            v[i] = m.get(i, i);
            index[i] = i;
        }

        for(int i = 0; i < v.length; i++){
            for(int j = i + 1; j < v.length; j++){
                if(Math.abs(v[i]) < Math.abs(v[j])){
                    double tmpValue = v[j];
                    v[j] = v[i];
                    v[i] = tmpValue;
                    int tmpIndex = index[j];
                    index[j] = index[i];
                    index[i] = tmpIndex;
                }
            }
        }

        return index;
    }
}
